# 二叉树中的最大路径和: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 这道题代码简单，最主要的是，你能分析出来！
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        """
            实际上就是，求当前节点的左边的最大路径值，和右边节点的最大路径值
            左右最大路径值 加上当前根节点的值， 就是以当前节点为根的 最大路径和

            而 每个节点为根， 都可能是整个树的最大路径值， 所以采用后序遍历 左，右，根。 
            找到最大的路径和

            需要注意的是，当有负数存在的时候， 要判断，取当前子节点路径最大和 和 0的最大值
        """
        maxSum = -1000
        def dfs(node):
            nonlocal maxSum

            if not node:
                return 0
            
            left = dfs(node.left)
            right = dfs(node.right)

            left = max(left, 0)
            right = max(right, 0)

            maxSum = max(maxSum, left + right + node.val)
            
            return max(left, right) + node.val


        dfs(root)
        return maxSum